package sort;

import java.util.Arrays;

public class HeapSort {
    public static void main(String args[]) {

        int[] arr = new int[]{123, 123, 12, 31, 23, 12, 31, 23, 12, 3};

        for (int i = arr.length - 1; i >= 0; i--) {
            int maxVal = arr[i];
            makeMaxHeap(arr, i - 1);
            if (arr[0] > maxVal) {
                arr[i] = arr[0];
                arr[0] = maxVal;
            }
        }
        System.out.println(Arrays.toString(arr));
    }


    public static void makeMaxHeap(int[] arr, int length) {
        //创建大根堆
        for (int i = length / 2 - 1; i >= 0; --i) {
            //取当前最深根
            int rootValue = arr[i];

            //取左节点位置
            int childIndex = 2 * i + 1;

            //比较左右节点的值
            if (childIndex + 1 < length && arr[childIndex] < arr[childIndex + 1])
                childIndex++;

            //与根值交换
            if (rootValue < arr[childIndex]) {
                arr[i] = arr[childIndex];
                arr[childIndex] = rootValue;
            }
        }
       // System.out.println(Arrays.toString(arr));
    }

}
